Data networks have become increasingly important in day-to-day activities and business applications. Most of these networks are a packet-switched network, such as the Internet, which uses a Transmission Control Protocol (TCP) and an Internet Protocol (IP), frequently referred to as TCP/IP. The Transmission Control Protocol manages the reliable reception and transmission of network traffic, while the Internet Protocol is responsible for routing to ensure that packets are sent to a correct destination.
In a typical network, a mesh of transmission links are provided, as well as switching nodes and end nodes. End nodes typically ensure that any packet is received and transmitted on the correct outgoing link to reach its destination. The switching nodes are typically referred to as packet switches, or routers, or intermediate systems. The sources and destinations in data traffic (the end nodes) can be referred to as hosts and end systems. These hosts and end systems typically are the personal computers, work stations and other terminals.
To help move information between computers, the open system interconnection (OSI) model has been developed. Each problem of moving information between computers is represented by a layer in the model, and thus, establishes a framework for standards. Two systems communicate only between layers in a protocol stack. However, it is desirable to communicate with a pure layer in the other system, and to achieve such results, information is exchanged by means of protocol data units (PDUs), also known as packets. The PDUs include headers that contain control information, such as addresses, as well as data. At a source, each layer adds its own header, as is well known to those skilled in the art. The seven layers, starting at the physical layer, include: (1) physical; (2) data link; (3) network; (4) transport; (5) session; (6) presentation; and (7) application layers.
The network systems typically use routers that can determine optimum paths, by using routing algorithms. The routers also switch packets arriving at an input port to an output port based on the routing path for each packet. The routing algorithms (or routing protocols) are used to initialize and maintain routing tables that consist of entries that point to a next router to send a packet with a given destination address. Typically, fixed costs are assigned to each link in the network and the cost reflects link bandwidth and/or costs. The least cost paths can be determined by a router after it exchanges network topology and link cost information with other routers.
The two lower layers, the physical and data link layers, are typically governed by a standard for local area networks developed by the IEEE 802 Committee. The data link layer is typically divided into two sublayers, the logical link control (LLC) sublayer, which defines functions such as framing, flow control, error control and addressing. The LLC protocol is a modification of the HDLC protocol. A medium access control (MAC) sublayer controls transmission access to a common medium.
High-level data link control (HDLC) is a communications control procedure for checking the accuracy of data transfer operations between remote devices, in which data is transferred in units known as frames, and in which procedures exist for checking the sequence of frames, and for detecting errors due to bits being lost or inverted during transfer operations. There are also functions which control the set-up and termination of the data link. In HDLC, the bit synchronous data communication across a transmission link is controlled. HDLC is included in the ITU packet-switching interface standard known as X0.25.
Programmable HDLC protocol controllers are commonly used in these systems. An HDLC controller is a computer peripheral-interface device which supports the International Standards Organization (ISO) high-level-data-link-control (HDLC). It reduces the central processing unit or microprocessor unit (MPU) software by supporting a frame-level instruction set and by hardware implementation of the low-level tasks associated with frame assembly-disassembly and data integrity.
Most communication protocols are bit-oriented, code-dependent, and ideal for full duplex communication. Some common applications include terminal-to-terminal, terminal-to-MPU, MPU-to-MPU, satellite communication, packet switching, and other high-speed data links.
A communication controller relieves a central MPU of many of the tasks associated with constructing and receiving frames. A frame (sometimes referred to as a packet) is a single communication element which can be used for both link-control and data-transfer purposes.
Most controllers include a direct memory access (DMA) device or function which provides access to an external shared memory resource. The controller allows either DMA or non-DMA data transfers. The controller accepts a command from the MPU, executes the command, and provides an interrupt and result back to the MPU.
Some HDLC controllers include various ports that have different interfaces (such as a 10 Mbps or as much as a 100 Mbps) which supports half or full duplex transmission. Some of the frames would move into a bus, and then into a direct memory access (DMA) unit where a CPU and ROM would be controlled by firmware having a dedicated instruction set. An interrupt would occur whenever a packet entered a port and the CPU would be interrupted. The firmware code would "drive" a command to the DMA and the packet would go out a shared external bus and get written into memory.
Any data structures, such as the HDLC controllers and other similar devices that receive and transmit frames, have a number of ways that they can be implemented to receive frames. Some have a dynamic memory allocation scheme, such as link lists and ring buffers. An alternate implementation employs link lists while others use a ring buffer, such as the first type of ring buffer algorithm that was implemented with the first Ethernet chip known as Market Lance MK 5032 and then later renamed the AMD 7990 chip.
Typically, in a ring buffer, there is a descriptor ring that has respective descriptors that describe and point to a respective frame data buffer within a shared system memory between the host and a controller. The descriptor ring is a circular queue with descriptor entries containing pointers and information for frame data buffers. Each descriptor ring is dedicated to a specific FIFO memory within the HDLC controller. Each two-word descriptor entry within a descriptor ring is associated with one specific buffer in a system memory, such as the shared system memory between a network device, such as a controller and host.
The frame data buffers are typically defined as blocks of memory (typically ranging from 512 to 2,048 bytes) containing frames for transmission or providing space for frame reception. Naturally, each transmit channel and each receive channel would use a dedicated descriptor ring. Whenever a frame exceeds the finite capacity of a single frame data buffer, the frame is said to "span" the buffer. An ownership bit in the first word of each descriptor indicates whether the host or controller owns the associated frame data buffer.
The ownership could follow a specific protocol that must be adhered to by the controller and the host. Once ownership of a descriptor has been relinquished to the other device or host, and been made part of the descriptor, its associated frame data buffer may be altered. The host gives the network device ownership of empty frame data buffers for frame reception and full frame data buffers for frame transmission. Conversely, the network device passes ownership back to the host for transmit frame data buffers it has used and receive frame data buffers it has filled.
For frame reception, the host is required to provide the controller or other network device with ownership of contiguous descriptors pointing to empty frame data buffers. Once a frame is fully received by the controller, ownership of its constituent descriptors is then reassigned. The host is signaled regarding the event via an interrupt. The host is typically obligated to read a register in order to surmise the meaning of the signal. Once this is accomplished, the frame may then be dispatched in some fashion and ownership of the relevant descriptors returned to the controller.
In a typical operation, the host "follows" the controller or other network device around the ring leaving "empty" descriptors in its wake for the controller to use. If the device gets too far ahead of the host, it can wrap around the descriptor ring and encounter descriptors it does not own. As a result, incoming frames could be lost if this occurs. For frame transmission, the device "follows" the host around a transmit descriptor ring leaving used descriptors in its wake for the host to reclaim. The host only gives the device ownership of descriptors when it has one or more frames ready for transmission. Once a frame is fully transmitted by the device, ownership of its constituent descriptors is passed back to the host for reuse. The host is signaled regarding this event via an interrupt.
In some applications, the host may elect to use frame data buffers which are smaller in size than the frames that are received as transmitters. In other words, a single frame may span multiple buffers. This type of system would allow frames to be dissected (scattered on reception) or assembled (gathered on transmission) by the controller. Multiple frame data buffers can hold the constituent pieces of a frame by "chaining" or grouping the associated descriptors together. By definition, the chained or grouped together descriptors are consecutive entries in a descriptor ring with the end-of-frame flag set in the terminating descriptor of the chain. The frame data buffer of a descriptor entry which is owned but whose end-of-frame flag (EOF) is not set is considered to be part of a frame and not an entire frame.
During the reception of large frames, the device "chains" or groups the descriptors together one by one as it fills each successive frame data buffer. When the end of the frame is received and transferred to the shared system memory, the end-of-frame flag is set in determining descriptor of the descriptor chain. During transmission, the controller is able to construct sequentially a single frame from the contents of chained buffers. Transmission of the frame terminates only when it encounters a buffer whose descriptor has set the end-of-frame flag.
In the known systems, each spanned descriptor was successively updated and altered. Thus, sufficient bus and CPU resources had to be allocated. This is an expensive operation for the host to accomplish. A command would have to be built and submitted to the DMA and the DMA would have to rearbitrate the bus with the firmware. The system bus would have to be arbitrated, while other devices may also be trying to access the system bus. Writing back all the descriptors in the descriptor chain uses enormous amount of resources.